// https://leetcode.cn/problems/integer-break/submissions/

// https://leetcode.cn/problems/jian-sheng-zi-lcof/ 剪绳子
class Solution {
public:
    int integerBreak(int n) {
        vector<int> ans(n + 1);
        ans[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j < i; ++j) {
                ans[i] = max(ans[i], max(j * (i - j), ans[j] * (i - j)));
                // 注意dp[i]对应的值是经过拆分了的，不拆分的情况要考虑
            }
        }
        return ans.back();
    }
};